package crack;

import org.junit.Test;

import java.util.ArrayList;

/**
 * @author fance
 * @date 18-4-1 上午11:53
 */
public class DP {
    public int cntWays(int n) {
        if (n < 0) {
            return 0;
        }
        if (n < 4) {
            return n;
        }
        int res = 0;
        int first = 3;
        int second = 2;
        int thrid = 1;
        for (int i = 4; i <= n; i++) {
            res = first + second + thrid;
            thrid = second;
            second = first;
            first = res;
        }
        return res;
    }
    public int cntWaysII(int n) {
        if (n < 0) {
            return 0;
        }
        if (n < 4) {
            return n;
        }
        return cntWaysII(n - 1) + cntWaysII(n - 2) + cntWaysII(n - 3);
    }


    /**
     * 适用与无重复值
     * 魔术索引: 数组有序  1. 暴力搜索 2. 利用有序的特性(a[i] > i 找左边 同理 a[i] < i 右边)
     * @param a
     * @return
     */
    public int magicSlow(int[] a) {
        return magicCore(a, 0, a.length - 1);
    }
    private int magicCore(int[] a, int st, int end) {
        if (end < st || st < 0 || end >= a.length) {
            return -1;
        }
        int mid = st + (end - st) / 2;
        if (a[mid] == mid) {
            return mid;
        } else if (a[mid] > mid) {
            return magicCore(a, st, mid - 1);
        } else {
            return magicCore(a, mid + 1, end);
        }
    }

    public int magicSlowMayHasDup(int[] a, int st, int end) {
        if (end < st || st < 0 || end >= a.length) {
            return -1;
        }
        int midIndex = st + (end - st) / 2;
        int midVal = a[midIndex];
        if (midIndex == midVal) {
            return midIndex;
        }

        int leftIndex = Math.min(midIndex - 1, midVal);
        int left = magicSlowMayHasDup(a, st, leftIndex);
        if (left >= 0) {
            return left;
        }
        int rightIndex = Math.max(midIndex + 1, midVal);
        int right = magicSlowMayHasDup(a, rightIndex, end);
        return right;
    }

    public ArrayList<ArrayList<Integer>> getSubSet(ArrayList<Integer> set, int index) {
        ArrayList<ArrayList<Integer>> res;
        if (set.size() == index) {
            res = new ArrayList<>();
            res.add(new ArrayList<>());
        } else {
            res = getSubSet(set, index + 1);
            int item = set.get(index);
            ArrayList<ArrayList<Integer>> moreSet = new ArrayList<>();
            for (ArrayList<Integer> subSet: res
                 ) {
                ArrayList<Integer> newSet = new ArrayList<>();
                newSet.addAll(subSet);
                newSet.add(item);
                moreSet.add(newSet);
            }
            res.addAll(moreSet);
        }
        return res;
    }
    @Test
    public void test() {
        System.out.println(cntWays(10));
        System.out.println(cntWaysII(10));

        /*System.out.println(magicSlow(new int[]{-1, 0, 2,3,}));
        System.out.println(magicSlowMayHasDup(new int[]{-1, -1,3, 3,3,}, 0, 4));
*/
    }
}
